package org.example.everyday;

import org.example.ch04.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/5/16 0016 9:38
 */
public class Lc2562 {
    public static void main(String[] args) {
        Lc2562 lc2562 = new Lc2562();




        TreeNode left = new TreeNode();
        left.val = 1;


        TreeNode right = new TreeNode();
        right.val = 3;


        TreeNode root = new TreeNode();
        root.val = 2;
        root.left = left;
        root.right = right;

        TreeNode p = new TreeNode();
        p.val = 3;

        TreeNode res =  lc2562.inorderSuccessor(root,p);
        System.out.println(res.val);





    }


    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        TreeNode prev = null,curr = root;
        while (!stack.isEmpty() || curr != null){
            while (curr != null){
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if(prev == p){
                return curr;
            }
            prev = curr;
            curr = curr.right;
        }
        return null;
    }
}
